interpolation search 為 binary search 的改良版
適合用在資料平均分佈的狀況下
其內插法公式為
mid = low + ((key – data[low]) / (data[high] – data[low])) * (high – low)
而其餘的搜尋步驟則與 binary search 差不多
平均而言其時間複雜度優於 O(log n)
interpolation search 為 binary search 的改良版
適合用在資料平均分佈的狀況下
其內插法公式為
mid = low + ((key – data[low]) / (data[high] – data[low])) * (high – low)
而其餘的搜尋步驟則與 binary search 差不多
平均而言其時間複雜度優於 O(log n)